#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2018/10/17 17:16
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : 队列&栈-打开转盘锁.py
# @Software: PyCharm


class Solution:
    def openLock(self, deadends, target):
        """
        :type deadends: List[str]
        :type target: str
        :rtype: int
        """
        used = {target: 1}
        mdead = {}
        que = [target]
        steps = {}
        ord_0 = ord('0')
        for i in range(10):
            c = chr(ord_0 + i)
            steps[c] = [chr(ord_0 + (i + 1) % 10), chr(ord_0 + (i + 9) % 10)]
        for s in deadends:
            mdead[s] = 1
        ans = 0
        while len(que) > 0:
            new_que = []
            ans += 1
            for cur in que:
                for i in range(4):
                    c = cur[i]
                    for j in range(2):
                        t = steps[c][j]
                        tt = cur[:i] + t + cur[i+1:]
                        if not used.get(tt) and not mdead.get(tt):
                            if tt == '0000':
                                return ans
                            new_que.append(tt)
                            used[tt] = 1
            que = new_que
        return -1





def main():
    solve = Solution()
    deadends = ["0201", "0101", "0102", "1212", "2002"]
    target = "0202"
    print(solve.openLock(deadends, target))


if __name__ == '__main__':
    main()
